882. Reachable Nodes In Subdivided Graph

https://leetcode.com/problems/reachable-nodes-in-subdivided-graph/

題目解釋

你有一個n 個點(node)組成的無向圖original graph；接著，有若干個點把這無向圖的邊(edge)切開，標示如下: edges[i] = [ui, vi, cnti] 代表點ui 到點vi 的邊之間插入了cnti 個點；最後，請回傳點0 (node 0) 在距離maxMove 之內可以接觸到幾個點。

example

解法

• 因為時間有點來不及，今天我就直接拿別人的解答來說明

這題雖然說edge 之間有新增若干個點，不過我們可以把這些點當作weight，這樣題目看起來就熟悉多了，就像是找最短路徑的那種題目，而今天正是要用Dijkstra's 演算法。

不過Dijkstra's 還不足以解決這題，因為Dijkstra's 只會保留最短路徑，而這題還另外要求在距離maxMove 內可以走到的點，那無向圖的邊就可能有以下幾種可能:

1. 邊是最短路徑
2. 邊長小於剩餘的maxMove 但是不是最短路徑
3. 邊長大於剩餘的maxMove

第一種狀況用Dijkstra's 就可以把路徑上的點算進來了；而第二第三種狀況的邊會被Dijkstra's 排除，則要另外把邊長算進來，此外第三種狀況的邊還需要計算走到兩側還剩餘多少maxMove。

不論如何都需要Dijkstra's 演算法，所以先上只有Dijkstra's 演算法的部分，也請參考看看Dijkstra's演算法的影片

Dijkstra's 演算法

class Solution(object):
    def reachableNodes(self, edges, M, N):
        graph = collections.defaultdict(dict)
        for u, v, w in edges:
            graph[u][v] = graph[v][u] = w

        pq = [(0, 0)] # 等待計算距離的點 [distance, node]
        dist = {0: 0} # 紀錄最短距離 {node: distance}

        while pq:
            d, node = heapq.heappop(pq)
            if d > dist[node]: continue

            for nei, weight in graph[node].items():
                d2 = d + weight + 1 # +1是因為點本身也佔一步距離
                if d2 < dist.get(nei, math.inf):
                    heapq.heappush(pq, (d2, nei))
                    dist[nei] = d2
                    # 更新最短路徑

        print(dist)

接著是可以通過本題的解法

程式碼

class Solution(object):
    def reachableNodes(self, edges, M, N):
        graph = collections.defaultdict(dict)
        for u, v, w in edges:
            graph[u][v] = graph[v][u] = w

        pq = [(0, 0)]
        dist = {0: 0}
        used = {}
        ans = 0

        while pq:
            d, node = heapq.heappop(pq)
            if d > dist[node]: continue
            ans += 1
            
            for nei, weight in graph[node].items():
                v = min(weight, M - d)
                used[node, nei] = v
                # min(weight, M - d)會把狀況二、三的邊長記下來
                # M - d代表到目前的點還剩多少步可以走，解決第三種狀況

                d2 = d + weight + 1
                if d2 < dist.get(nei, M+1):
                    heapq.heappush(pq, (d2, nei))
                    dist[nei] = d2

        for u, v, w in edges:
            ans += min(w, used.get((u, v), 0) + used.get((v, u), 0))

        return ans

閒聊

Dijkstra真的很厲害，除了這個演算法外，他還有另一個知名的Banker's algorithm

但是他的名字太難記了，所以我都叫Dijkstra's 演算法為大DD演算法